This invention is directed to locating a particular record in a database containing a plurality of records.
A typical database can accommodate a plurality of records each having a number of different fields. Locating a record or a group of records using a predetermined search criteria such as a particular name in a last name field can be accomplished by sequentially searching each record and making a comparison of the data contained in the last name field with the desired last name. In order to insure that all records have been located matching the search criteria, all records must be searched. The time required for such a search depends upon the number of records in the database and the complexity of the search criteria.
In some database applications the identity of a particular record will be known since identifying data in one or more fields is available. In this situation the objective is to quickly locate the particular record in an unsorted database so that the full record can be accessed or in order to modify the data in the record. A direct approach for locating a desired record(s) is to sequentially search the records to locate the record(s) having data in one or more fields that is equal to the search criteria data. However, this method is relatively inefficient. This is especially apparent where the record identification criteria may locate more than one record in the database, thereby requiring a search of all records in order to insure that the appropriate records have all been located.
It is known to utilize a table in which a unique identifier for each record is stored as one entry with the corresponding address of the record stored as a second entry for each record. Thus, to locate a record, only the table need be searched as opposed to a search of the records themselves. Although this technique is more efficient than directly searching the records, on a statistical basis a search of 50 percent of the number of entries in the unsorted table will be required to locate the identifier in the table.
A number of applications exist in which identification criteria for a particular record is known. Thus, the challenge exists in efficiently locating the particular record in the database. A database in a telecommunications switch contains parameters which reflect features selected by customers to be utilized for their telephone service. In order to maintain the database, it is desirable to be able to search the database to locate specific records and verify correct relationships between records.
A database utilized to identify library materials represents another example in which it is desirable to be able to locate a predetermined record based upon a known search criteria such as by a unique identifying number. The records may be required to be located in order to update the record to reflect that material is checked out to a given individual. To check out a book from a library, a librarian enters a unique number for a book into a database so that the corresponding record can be updated to reflect that the book has been checked out to a specific person on a particular date. In order to minimize the time required to locate a particular record, there exists a need for an improved record location technique which allows a record to be more quickly located than a sequential search of the database.